package com.rui.heiMa.sort;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : Quick
 * @createTime : [2022/2/15 21:18]
 * @description : [快速排序]
 */

@SuppressWarnings("all")
public class Quick {

    /**
     * 比较v元素是否小于w元素
     * @param v 元素v
     * @param w 元素w
     * @return boolean
     */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 数组元素i和j交换
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 对数组内部的元素进行排序
     */
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a,lo,hi);
    }

    /**
     * 对数组a中从索引lo到索引hi的元素进行排序
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        //安全性校验
        if(hi <= 0){
            return;
        }

        //需要对数组中lo索引到hi索引处的元素进行分组 分为左子组和右子组  返回的是分界值所在的索引
        int partition = partition(a, lo, hi);

        //对左子组进行排序
        sort(a, lo, partition - 1);

        //对右子组进行排序
        sort(a, partition + 1, hi);
    }

    /**
     * 对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分割界限对应的索引
     */
    public static int partition(Comparable[] a, int lo, int hi) {
        //确定分界值
        Comparable key = a[lo];

        //定义两个指针 分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi + 1;

        //切分
        while (true) {
            //从右边开始找到第一个小于key的元素
            while(less(key, a[--right])){
                if(right == lo){
                    break;
                }
            }
            //从左边开始找到第一个大于key的元素
            while (less(a[++left], key)){
                if(left == right){
                    break;
                }
            }

            //判断left是否大于等于right，如果是，则说明已经找到分界值，如果不是，则交换
            if(left >= right){
                break;
            }else {
                exch(a, left, right);
            }
        }

        //交换分界值
        exch(a, lo, right);

        return right;
    }
}
